home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_10_03 / 1003021a < prev    next >
Encoding:
Text File  |  1991-12-17  |  2.4 KB  |  104 lines
  1.  
  2. #include <ctype.h>
  3.  
  4. void push(int);
  5. int pop(void);
  6.  
  7. /*--------------------------------------------------------------------
  8.  
  9. FUNCTION: intopost - converts infix to postfix
  10.  
  11. A.  Push a ( on the stack.  This sentinel allows us to detect when we have
  12. flushed out the stack on completion in step I.
  13.  
  14. --- Perform steps B through H for each character in the infix string ---
  15.  
  16. B.  Ignore white space.
  17.  
  18. C.  Pass alphabetic characters through to postfix list.
  19.  
  20. D.  Push any ( on the stack.  These sentinels allows us to detect when we
  21. have flushed out the stack when handling ) and operators.
  22.  
  23. E.  Have a ) so pop off the stack and put into postfix list until a ( is
  24. popped.  Discard that (.
  25.  
  26. F.  Have a * or /.  Pop off any operators of equal or higher precedence
  27. and put them into postfix list.  If a ( or lower precedence operator (such
  28. as + or -) is popped, put it back and stop looking.  Push new * or /.
  29.  
  30. G.  Have a + or -.  Pop off any operators of equal or higher precedence
  31. (that includes all of them) and put them into postfix list.  If a ( is
  32. popped, put it back and stop looking.  Push new + or -.
  33.  
  34. H.  Report unknown character on input.
  35.  
  36. ------
  37.  
  38. I.  Have processed all input characters.  Now flush stack until we find
  39. the matching ( put there in step A.
  40.  
  41. J.  Terminate the postfix list.
  42.  
  43. --------------------------------------------------------------------*/
  44.  
  45. void intopost(const char *infix, char *postfix)
  46. {
  47.     int st;
  48.  
  49. /*A*/    push('(');
  50.     while (*infix != '\0') {
  51.  
  52. #ifdef TRACE
  53. printf("*infix: %c\n", *infix);
  54. #endif
  55.  
  56. /*B*/        if (isspace(*infix)) {
  57.             ;
  58.         }
  59. /*C*/        else if (isalpha(*infix)) {
  60.             *postfix++ = *infix;
  61.         }
  62. /*D*/        else if (*infix == '(') {
  63.             push('(');
  64.         }
  65. /*E*/        else if (*infix == ')') {
  66.             while ((st = pop()) != '(')
  67.                 *postfix++ = st;
  68.         }
  69. /*F*/        else if (*infix == '*' || *infix == '/') {
  70.             while (1) {
  71.                 if ((st = pop()) == '(' || st == '+'
  72.                     || st == '-') {
  73.                     push(st);
  74.                     break;
  75.                 }
  76.                 *postfix++ = st;
  77.             }
  78.             push(*infix);
  79.         }
  80. /*G*/        else if (*infix == '+' || *infix == '-') {
  81.             while (1) {
  82.                 if ((st = pop()) == '(') {
  83.                     push(st);
  84.                     break;
  85.                 }
  86.                 *postfix++ = st;
  87.             }
  88.             push(*infix);
  89.         }
  90. /*H*/        else {
  91.             printf("Unknown input character %c\n", *infix);
  92.         }
  93.  
  94.         ++infix;
  95.         continue;
  96.     }
  97.  
  98. /*I*/    while ((st = pop()) != '(')
  99.         *postfix++ = st;
  100.  
  101. /*J*/    *postfix = '\0';
  102. }
  103.  
  104.